#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <map>
#include <deque>

using namespace std;


class Solution {
public:
	// 这种情况是超时的 暴力方法
    vector<vector<int>> threeSum(vector<int>& nums) {
		int nSize = nums.size();
		if(nSize < 3){
			return {};
		}
		sort(nums.begin(), nums.end());
		// for(auto i : nums){
			// cout << i << " ";
		// }
		// cout << endl;
		vector<vector<int>> res;

		for(int i = 0; i < nSize - 2; i++){
			if(i > 0 && nums[i] == nums[i-1]){
				continue;
			}
            if(nums[i] + nums[i+1] + nums[i+2] > 0){
                return res;
            }
			for(int j = i + 1; j < nSize - 1; j++){
                if(j > i+1 && nums[j] == nums[j-1]){
                    continue;
                }
                if(nums[i] + nums[j] + nums[j+1] > 0){
                    break;
                }
				for(int k = j + 1; k < nSize; k++){
					if(binary_search(nums.begin() + j + 1, nums.end(), -(nums[i]+nums[j]))){
                        cout << 123 << endl;
						res.push_back({nums[i],nums[j], -(nums[i]+nums[j])});
						break;
					}
				}
			}
		}
		return res;
    }
	
	// 双指针法
	vector<vector<int>> threeSum1(vector<int>& nums) {
		int len = nums.size();
		if(len < 3){
			return {};
		}
		sort(nums.begin(), nums.end());
		vector<vector<int>> res;
		for(int i = 0; i < len; i++){
			// 这种后置写法，可以确保{-1,-1,2} | {-1,0,-1} 类似这种首个元素重复的情况  
			if(i > 0 && nums[i] == nums[i-1]){
				continue;
			}
			int left = i+1;
			int right = len - 1;
			while(left < right){
				if(left < right && nums[i] + nums[left] + nums[right] < 0){
					left++;
					continue;
				}
				if(left < right && nums[i] + nums[left] + nums[right] > 0){
					right--;
					continue;
				}
				if(nums[i] + nums[left] + nums[right] == 0){
					res.push_back({nums[i], nums[left], nums[right]});
					while(nums[left] == nums[left+1] && left < len - 2){
						left++;
					}
					left++;
					while(nums[right] == nums[right-1] && right > i+2){
						right--;
					}
					right--;
				}
			}
		}
		return res;
	}
};

int main(){
	Solution so;
	vector<int> input = {0,0,0};
	vector<vector<int>> a = so.threeSum1(input);
	for(auto items : a){
		cout << "[";
		for(auto i : items){
			cout << i << ",";
		}
		cout << "]";
	}
	return 0;
}